#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <vector>

#include <iostream>
#include <algorithm>
using namespace std;

//class Solution {
//public:
//    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//        int m = nums1.size();
//        int n = nums2.size();
//        int num = n + m;
//        if (num == 0)
//        {
//            return 0;
//        }
//        vector<int> p;
//        for (int i = 0; i < m; i++)
//        {
//            p.push_back(nums1[i]);
//        }
//        for (int i = 0; i < n; i++)
//        {
//            p.push_back(nums2[i]);
//        }
//        sort(p.begin(), p.end());
//        if (num % 2 == 0)
//        {
//            return (p[num / 2] + p[(num / 2) - 1]) / 2.0;
//        }
//        else
//        {
//            return p[num / 2];
//        }
//    }
//};
//
//int main()
//{
//    system("pause");
//    return 0;
//}

typedef struct ListNode
{
    int num;
    struct ListNode* next;
}ListNode;
//
//class Solution {
//public:
//    void Num(ListNode* head)
//    {
//        while (head != NULL)
//        {
//            my_num++;
//            head = head->next;
//        }
//    }
//    ListNode* removeNthFromEnd(ListNode* head, int n)
//    {
//        Num(head);
//        if (my_num > n)
//        {
//            ListNode* p = head;
//            int i = 1;
//            while (i != my_num - n)
//            {
//                p = p->next;
//                i++;
//            }
//            if (n == 1)
//            {
//                delete p->next;
//                p->next = NULL;
//            }
//            else
//            {
//                ListNode* k = p->next->next;
//                delete p->next;
//                p->next = k;
//            }
//            return head;
//        }
//        else if (my_num = n)
//        {
//            ListNode* p = head->next;
//            delete head;
//            head = NULL;
//            return p;
//        }
//        else
//        {
//            return NULL;
//        }
//    }
//    size_t my_num = 0;
//    void Print(ListNode* head)
//    {
//        while (head != NULL)
//        {
//            cout << head->num << " ";
//            head = head->next;
//        }
//    }
//};
//
//int main()
//{
//    ListNode* p1;
//    p1 = new ListNode;
//    ListNode* p2;
//    p2 = new ListNode;
//    ListNode* p3;
//    p3 = new ListNode;
//    ListNode* p4;
//    p4 = new ListNode;
//    ListNode* p5;
//    p5 = new ListNode;
//    p1->num = 1;
//    p2->num = 2;
//    p3->num = 3;
//    p4->num = 4;
//    p5->num = 5;
//    p1->next = p2;
//    p2->next = p3;
//    p3->next = p4;
//    p4->next = p5;
//    p5->next = NULL;
//    Solution p;
//    ListNode* pt = p.removeNthFromEnd(p1, 2);
//    p.Print(pt);
//    system("pause");
//    return 0;
//}

//class Solution {
//public:
//    int strStr(string haystack, string needle)
//    {
//        int m = 0;
//        int n = m;
//        int ret = -1;
//        while (haystack[m] != 0)
//        {
//            ret = 0;
//            n = m;
//            while (haystack[n] == needle[ret])
//            {
//                n++;
//                ret++;
//                if (needle[ret] == '\0')
//                {
//                    return m;
//                }
//            }
//            m++;
//        }
//        return -1;
//    }
//};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* ret;
        if (head == NULL)
        {
            return NULL;
        }
        else if (head->next != NULL)
        {
            ret = head->next;
        }
        else
        {
            ret = head;
        }
        ListNode* rp = new ListNode;
        while (head != NULL && head->next != NULL)
        {
            ListNode* p = head->next->next;
            ListNode* p1 = head->next;
            head->next = p;
            p1->next = head;
            rp->next = p1;
            rp = head;
            head = head->next;
        }
        return ret;
    }
    void Print(ListNode* p)
    {
        while (p != NULL)
        {
            cout << p->num << " ";
            p = p->next;
        }
    }
};

int main()
{
    ListNode* p1 = new ListNode;
    ListNode* p2 = new ListNode;
    ListNode* p3 = new ListNode;
    ListNode* p4 = new ListNode;
    p1->num = 1;
    p2->num = 2;
    p3->num = 3;
    p4->num = 4;
    p1->next = p2;
    p2->next = p3;
    p3->next = p4;
    p4->next = NULL;
    Solution p;
    ListNode* pp= p.swapPairs(p1);
    p.Print(pp);
    return 0;
}